//==================================================================
//  Copyright (C) 2006  Davide Pasca
//
//  This library is free software; you can redistribute it and/or
//  modify it under the terms of the GNU Lesser General Public
//  License as published by the Free Software Foundation; either
//  version 2.1 of the License, or (at your option) any later version.
//
//  This library is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//  Lesser General Public License for more details.
//
//  You should have received a copy of the GNU Lesser General Public
//  License along with this library; if not, write to the Free Software
//  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
//==================================================================
//==
//==
//==
//==================================================================

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#include "m5d_scene.h"
#include "m5d_mesh.h"
#include "m5d_tvert.h"

//==================================================================
using namespace M5D;

//==================================================================
static void calc_mesh_bbox( Vector3 &bmin, Vector3 &bmax, const Vector3 *posp, int nv )
{
	bmin._x = bmax._x = posp->_x;
	bmin._y = bmax._y = posp->_y;
	bmin._z = bmax._z = posp->_z;

	for (; nv > 0; --nv)
	{
		if ( posp->_x < bmin._x )	bmin._x = posp->_x;
		if ( posp->_y < bmin._y )	bmin._y = posp->_y;
		if ( posp->_z < bmin._z )	bmin._z = posp->_z;

		if ( posp->_x > bmax._x )	bmax._x = posp->_x;
		if ( posp->_y > bmax._y )	bmax._y = posp->_y;
		if ( posp->_z > bmax._z )	bmax._z = posp->_z;

		posp += 3;
	}
}

//==================================================================
static float find_closest_non_intersecting_plane( float start_val,
												  int coord_idx,
												  const Triangle	*trigsp,
												  int				trigs_n,
												  const Vector3 *posp )
{
float	min_adjust, max_adjust;

	min_adjust = max_adjust = start_val;

	const Triangle	*trip		= trigsp;
	const Triangle	*trip_end	= trigsp + trigs_n;
	for (; trip < trip_end; ++trip)
	{
	float		t, tmin, tmax;

		// calculate min and max values for the triangle
		tmin = tmax = posp[ trip->pos[0] ]._v[ coord_idx ];

		t = posp[ trip->pos[1] ]._v[ coord_idx ];
		if ( t < tmin )	tmin = t;
		if ( t > tmax )	tmax = t;

		t = posp[ trip->pos[2] ]._v[ coord_idx ];
		if ( t < tmin )	tmin = t;
		if ( t > tmax )	tmax = t;

		// if the plane intersets this triangle, then adjust the current values
		if ( start_val > tmin && start_val < tmax )
		{
			if ( tmin < min_adjust )
				min_adjust = tmin;

			if ( tmax > max_adjust )
				max_adjust = tmax;
		}
	}

//	float	diff_max = max_adjust - start_val;
//	float	diff_min = start_val - min_adjust;

//	if ( diff_max < diff_min )
		return max_adjust;
//	else
//		return min_adjust;
}

//==================================================================
Mesh *Mesh::move_mesh_geom( std::vector<int> &tri_list, int name_cnt )
{
	Mesh	*new_meshp;

	char	buff[ 1024 ];	// $$$
	sprintf_s( buff, "%s %i", _mod_name, name_cnt );

	new_meshp = _mod_scenep->NewMesh( buff );

	//---------------------------
	try
	{
		new_meshp->_geomp->GetVerts().CopyFrom( _geomp->GetVerts() );
	}
	catch (...)
	{
		if ( new_meshp )
			_mod_scenep->DeleteModel( (Model *)new_meshp );

		throw;
	}

	try
	{
		new_meshp->GetTrigs().LockRW( __FILE__, __LINE__ );
		_geomp->GetTrigs().LockR( __FILE__, __LINE__ );

		for (int i=0; i < tri_list.size(); ++i)
		{
			int			tidx;

			tidx = tri_list[i];

			Triangle	&src_tri = GetTriangle( tidx );

			if ( src_tri.IsValid() )
			{
				new_meshp->msh_trig_addcopy( &_geomp->GetTrigs()._list[ tidx ] );
				src_tri.Invalidate();
			}
		}

		new_meshp->GetTrigs().Unlock();
		_geomp->GetTrigs().Unlock();

		//---------------------------
		for (int i=0; i < VType::N; ++i)
		{
			new_meshp->eliminateUnusedVerts( (VType::VType)i );
		}
		//new_meshp->ext_eliminate_unused_pos_verts();

		//new_meshp->msh_trigs_normals_calc();

		// any self-respecting group should have all updated in the end
		new_meshp->UpdateGeometry();

		// finally add the new mesh as a child of the current one
		AddChild( new_meshp );

		return new_meshp;
	}
	catch (...)
	{
		if ( new_meshp )
			_mod_scenep->DeleteModel( (Model *)new_meshp );

		throw;
	}
}

//==================================================================
static void autogroups_move_geom( Mesh *desp, Mesh *srcp,
									TriIdx_VertIdx &tidx_vidx,
									float min_coord, float max_coord, int coord_idx )
{
	desp->_geomp->GetVerts().CopyFrom( srcp->_geomp->GetVerts() );

	if ERR_FALSE( tidx_vidx.len() == desp->_geomp->GetVerts().GetPosN() )
	{
		throw "wooooo !";
	}

	Vector3		*posp = srcp->_geomp->GetVerts().GetPosW();

	int	nelim=0;
	
	for (int i=0; i < tidx_vidx.len(); ++i, posp += 3)
	{
		TriList		&trilist = tidx_vidx[ i ];

		if ( !tidx_vidx.IsVertMarkedForRemoval( i ) &&
			 posp->_v[ coord_idx ] > min_coord && posp->_v[ coord_idx ] <= max_coord )
		{
			for (int j=0; j < trilist.len(); ++j)
			{
				int tidx = trilist[j];

				Triangle	&src_tri = srcp->GetTriangle( tidx );
				if ( src_tri.IsValid() )
				{
					desp->msh_trig_addcopy( &srcp->_geomp->GetTriangle( tidx ) );
					src_tri.Invalidate();
					++nelim;
				}
			}
			tidx_vidx.MarkVertForRemoval( i );
		}
	}
	desp->killUnusedPosVerts();
}


//==================================================================
#define CHECK_FOR_SPLIT_TMP_FLG	1
#define REMOVE_TMP_FLG			2

//==================================================================
class bbox_c
{
public:
	Vector3	_bmin, _bmax;
	//==================================================================
	void reset()
	{
		_bmin._v[0] = _bmin._v[1] = _bmin._v[2] =  10e+10;
		_bmax._v[0] = _bmax._v[1] = _bmax._v[2] = -10e+10;
	}
	//==================================================================
/*	bbox_c()
	{
		reset();
	}
*/	//==================================================================
	void update( const Vector3 &vec )
	{
		if ( vec._v[0] < _bmin._v[0] )	_bmin._v[0] = vec._v[0];
		if ( vec._v[1] < _bmin._v[1] )	_bmin._v[1] = vec._v[1];
		if ( vec._v[2] < _bmin._v[2] )	_bmin._v[2] = vec._v[2];
		if ( vec._v[0] > _bmax._v[0] )	_bmax._v[0] = vec._v[0];
		if ( vec._v[1] > _bmax._v[1] )	_bmax._v[1] = vec._v[1];
		if ( vec._v[2] > _bmax._v[2] )	_bmax._v[2] = vec._v[2];
	}
	//==================================================================
	void update( float x, float y, float z )
	{
		if ( x < _bmin._v[0] )	_bmin._v[0] = x;
		if ( y < _bmin._v[1] )	_bmin._v[1] = y;
		if ( z < _bmin._v[2] )	_bmin._v[2] = z;
		if ( x > _bmax._v[0] )	_bmax._v[0] = x;
		if ( y > _bmax._v[1] )	_bmax._v[1] = y;
		if ( z > _bmax._v[2] )	_bmax._v[2] = z;
	}
	//==================================================================
	void expand( float v )
	{
		_bmin._v[0] -= v;
		_bmin._v[1] -= v;
		_bmin._v[2] -= v;
		_bmax._v[0] += v;
		_bmax._v[1] += v;
		_bmax._v[2] += v;
	}
	//==================================================================
	bool contains( const Vector3 &vec )
	{
		return ( vec._v[0] >= _bmin._v[0] && vec._v[1] >= _bmin._v[1] && vec._v[2] >= _bmin._v[2] &&
				 vec._v[0] <= _bmax._v[0] && vec._v[1] <= _bmax._v[1] && vec._v[2] <= _bmax._v[2] );
	}
};

//==================================================================
enum {
	X, Y, Z
};
#define CROSS(dest,v1,v2) \
          dest[0]=v1[1]*v2[2]-v1[2]*v2[1]; \
          dest[1]=v1[2]*v2[0]-v1[0]*v2[2]; \
          dest[2]=v1[0]*v2[1]-v1[1]*v2[0]; 

#define DOT(v1,v2) (v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2])

#define SUB(dest,v1,v2) \
          dest[0]=v1[0]-v2[0]; \
          dest[1]=v1[1]-v2[1]; \
          dest[2]=v1[2]-v2[2]; 

#define FINDMINMAX(x0,x1,x2,min,max) \
  min = max = x0;   \
  if(x1<min) min=x1;\
  if(x1>max) max=x1;\
  if(x2<min) min=x2;\
  if(x2>max) max=x2;

//==================================================================
static int planeBoxOverlap( const float normal[3], const float vert[3], const float maxbox[3])	// -NJMP-
{
int q;
float vmin[3],vmax[3],v;

	for(q=X;q<=Z;q++)
	{
		v=vert[q];					// -NJMP-
		if(normal[q]>0.0f)
		{
			vmin[q]=-maxbox[q] - v;	// -NJMP-
			vmax[q]= maxbox[q] - v;	// -NJMP-
		}
		else
		{
			vmin[q]= maxbox[q] - v;	// -NJMP-
			vmax[q]=-maxbox[q] - v;	// -NJMP-
		}
	}

	if ( DOT(normal,vmin) >  0.0f )	return 0;	// -NJMP-
	if ( DOT(normal,vmax) >= 0.0f )	return 1;	// -NJMP-

	return 0;
}

/*======================== X-tests ========================*/
#define AXISTEST_X01(a, b, fa, fb)			   \
	p0 = a*v0[Y] - b*v0[Z];			       	   \
	p2 = a*v2[Y] - b*v2[Z];			       	   \
        if(p0<p2) {min=p0; max=p2;} else {min=p2; max=p0;} \
	rad = fa * boxhalfsize[Y] + fb * boxhalfsize[Z];   \
	if(min>rad || max<-rad) return 0;

#define AXISTEST_X2(a, b, fa, fb)			   \
	p0 = a*v0[Y] - b*v0[Z];			           \
	p1 = a*v1[Y] - b*v1[Z];			       	   \
        if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} \
	rad = fa * boxhalfsize[Y] + fb * boxhalfsize[Z];   \
	if(min>rad || max<-rad) return 0;

/*======================== Y-tests ========================*/
#define AXISTEST_Y02(a, b, fa, fb)			   \
	p0 = -a*v0[X] + b*v0[Z];		      	   \
	p2 = -a*v2[X] + b*v2[Z];	       	       	   \
        if(p0<p2) {min=p0; max=p2;} else {min=p2; max=p0;} \
	rad = fa * boxhalfsize[X] + fb * boxhalfsize[Z];   \
	if(min>rad || max<-rad) return 0;

#define AXISTEST_Y1(a, b, fa, fb)			   \
	p0 = -a*v0[X] + b*v0[Z];		      	   \
	p1 = -a*v1[X] + b*v1[Z];	     	       	   \
        if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} \
	rad = fa * boxhalfsize[X] + fb * boxhalfsize[Z];   \
	if(min>rad || max<-rad) return 0;

/*======================== Z-tests ========================*/
#define AXISTEST_Z12(a, b, fa, fb)			   \
	p1 = a*v1[X] - b*v1[Y];			           \
	p2 = a*v2[X] - b*v2[Y];			       	   \
        if(p2<p1) {min=p2; max=p1;} else {min=p1; max=p2;} \
	rad = fa * boxhalfsize[X] + fb * boxhalfsize[Y];   \
	if(min>rad || max<-rad) return 0;

#define AXISTEST_Z0(a, b, fa, fb)			   \
	p0 = a*v0[X] - b*v0[Y];				   \
	p1 = a*v1[X] - b*v1[Y];			           \
        if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} \
	rad = fa * boxhalfsize[X] + fb * boxhalfsize[Y];   \
	if(min>rad || max<-rad) return 0;

typedef float	float3[3];

//==================================================================
static int triBoxOverlap( const float boxcenter[3], const float boxhalfsize[3],
						  const float3 vert0, const float3 vert1, const float3 vert2,
						  const float3 normal  )
{
	/*    use separating axis theorem to test overlap between triangle and box */
	/*    need to test for overlap in these directions: */
	/*    1) the {x,y,z}-directions (actually, since we use the AABB of the triangle */
	/*       we do not even need to test these) */
	/*    2) normal of the triangle */
	/*    3) crossproduct(edge from tri, {x,y,z}-directin) */
	/*       this gives 3x3=9 more tests */
	float	v0[3],v1[3],v2[3];
	//   float axis[3];
	float	min,max,p0,p1,p2,rad,fex,fey,fez;		// -NJMP- "d" local variable removed
	float	e0[3],e1[3],e2[3];

	/* This is the fastest branch on Sun */
	/* move everything so that the boxcenter is in (0,0,0) */
	SUB(v0,vert0,boxcenter);
	SUB(v1,vert1,boxcenter);
	SUB(v2,vert2,boxcenter);

	/* compute triangle edges */
	SUB(e0,v1,v0);      /* tri edge 0 */
	SUB(e1,v2,v1);      /* tri edge 1 */
	SUB(e2,v0,v2);      /* tri edge 2 */

	/* Bullet 3:  */
	/*  test the 9 tests first (this was faster) */
	fex = fabsf(e0[X]);
	fey = fabsf(e0[Y]);
	fez = fabsf(e0[Z]);
	AXISTEST_X01(e0[Z], e0[Y], fez, fey);
	AXISTEST_Y02(e0[Z], e0[X], fez, fex);
	AXISTEST_Z12(e0[Y], e0[X], fey, fex);

	fex = fabsf(e1[X]);
	fey = fabsf(e1[Y]);
	fez = fabsf(e1[Z]);
	AXISTEST_X01(e1[Z], e1[Y], fez, fey);
	AXISTEST_Y02(e1[Z], e1[X], fez, fex);
	AXISTEST_Z0(e1[Y], e1[X], fey, fex);

	fex = fabsf(e2[X]);
	fey = fabsf(e2[Y]);
	fez = fabsf(e2[Z]);
	AXISTEST_X2(e2[Z], e2[Y], fez, fey);
	AXISTEST_Y1(e2[Z], e2[X], fez, fex);
	AXISTEST_Z12(e2[Y], e2[X], fey, fex);

	/* Bullet 1: */
	/*  first test overlap in the {x,y,z}-directions */
	/*  find min, max of the triangle each direction, and test for overlap in */
	/*  that direction -- this is equivalent to testing a minimal AABB around */
	/*  the triangle against the AABB */

	/* test in X-direction */
	FINDMINMAX(v0[X],v1[X],v2[X],min,max);
	if(min>boxhalfsize[X] || max<-boxhalfsize[X]) return 0;

	/* test in Y-direction */
	FINDMINMAX(v0[Y],v1[Y],v2[Y],min,max);
	if(min>boxhalfsize[Y] || max<-boxhalfsize[Y]) return 0;

	/* test in Z-direction */
	FINDMINMAX(v0[Z],v1[Z],v2[Z],min,max);
	if(min>boxhalfsize[Z] || max<-boxhalfsize[Z]) return 0;

	/* Bullet 2: */
	/*  test if the box intersects the plane of the triangle */
	/*  compute plane equation of triangle: normal*x+d=0 */

	// -NJMP- (line removed here)
	if(!planeBoxOverlap(normal,v0,boxhalfsize)) return 0;	// -NJMP-

	return 1;   /* box and triangle overlaps */
}

//==================================================================
static void expand_bbox_by_contained_triangles(bbox_c			&bbox,
												std::vector<int>		&trilist_a,
												const Vector3	*pos_vertsp,
												Triangle		*trigsp,
												int				trigs_n ) throw(...)
{
	Vector3	bbox_center;
	Vector3	bbox_halfsize;

	bbox_center = (bbox._bmin + bbox._bmax) * 0.5f;
	bbox_halfsize = (bbox._bmax - bbox._bmin) * 0.5f;

	for (Triangle *tp=trigsp; tp != trigsp + trigs_n; ++tp)
	{
		if NOT( tp->flags & Triangle::MESHSPLIT_TMP_FLG )
		{
			if ( triBoxOverlap( bbox_center._v, bbox_halfsize._v,
								pos_vertsp[ tp->pos[0] ]._v,
								pos_vertsp[ tp->pos[1] ]._v,
								pos_vertsp[ tp->pos[2] ]._v,
								(float *)tp->tplane._v  ) )
			{
				// update the boinding box with the vertices used in this triangle
				bbox.update( pos_vertsp[ tp->pos[0] ] );
				bbox.update( pos_vertsp[ tp->pos[1] ] );
				bbox.update( pos_vertsp[ tp->pos[2] ] );

				bbox_center = (bbox._bmin + bbox._bmax) * 0.5f;
				bbox_halfsize = (bbox._bmax - bbox._bmin) * 0.5f;

				trilist_a.push_back( tp - trigsp );

				tp->flags |= Triangle::MESHSPLIT_TMP_FLG;
			}
		}
	}
/*
	tri_list_t	*tlistp = tidx_vidx._tri_lists;
	for (int vidx=0; vidx < tidx_vidx._tri_lists.len(); ++vidx, ++tlistp)
	{
		if ( bbox.contains( pos_vertsp[ vidx ] ) )
		{
			for (int i=0; i < tlistp->_n_tris; ++i)
			{
				int		tidx = tlistp->_trilistp[ i ];

				if NOT( trigsp[ tidx ].flags & triangle_t::MESHSPLIT_TMP_FLG )
				{
					triangle_t	*trip		= trigsp + tidx;
					float4			*triplane	= &trigsp[ tidx ].tplane;

					if ( triBoxOverlap( bbox_center, bbox_halfsize,
									pos_vertsp[ trip->pos[0] ],
									pos_vertsp[ trip->pos[1] ],
									pos_vertsp[ trip->pos[2] ],
									(float *)triplane[0]  ) )
					{
						// update the boinding box with the vertices used in this triangle
						bbox.update( pos_vertsp[ trip->pos[0] ] );
						bbox.update( pos_vertsp[ trip->pos[1] ] );
						bbox.update( pos_vertsp[ trip->pos[2] ] );

						if ( trilist_a.append( tidx ) )
							return KERROR;

						trigsp[ tidx ].flags |= triangle_t::MESHSPLIT_TMP_FLG;
					}
				}
			}
		}
	}
*/
}

//==================================================================
static PError expand_bbox_by_connected_triangles( bbox_c			&bbox,
												std::vector<int>			*out_trilistp,
												const Vector3		*pos_vertsp,
												const TriIdx_VertIdx	&tidx_vidx,
												Triangle			*trigsp,
												int					cur_tvidx )
{
	const TriList	&trilist = tidx_vidx[ cur_tvidx ];

	for (int i=0; i < trilist.len(); ++i)
	{
		int			tr_i = trilist[i];

		Triangle	*trip = &trigsp[ tr_i ];

		if NOT( trip->flags & Triangle::MESHSPLIT_TMP_FLG )
		{
			trip->flags |= Triangle::MESHSPLIT_TMP_FLG;

			out_trilistp->push_back( tr_i );

			// update the bounding box with the vertices used in this triangle
			bbox.update( pos_vertsp[ trip->pos[0] ] );
			bbox.update( pos_vertsp[ trip->pos[1] ] );
			bbox.update( pos_vertsp[ trip->pos[2] ] );

			// recourse into the vertices of this triangle (avoiding the obvious current one)
			if ( trip->pos[0] != cur_tvidx )
				if ( expand_bbox_by_connected_triangles( bbox, out_trilistp, pos_vertsp, tidx_vidx, trigsp, trip->pos[0] ) )
					return PERROR;							 
														 
			if ( trip->pos[1] != cur_tvidx )					 
				if ( expand_bbox_by_connected_triangles( bbox, out_trilistp, pos_vertsp, tidx_vidx, trigsp, trip->pos[1] ) )
					return PERROR;							 
														 
			if ( trip->pos[2] != cur_tvidx )					 
				if ( expand_bbox_by_connected_triangles( bbox, out_trilistp, pos_vertsp, tidx_vidx, trigsp, trip->pos[2] ) )
					return PERROR;
		}
	}

	return POK;
}

//==================================================================
void Mesh::msh_split_submeshes( int max_verts_per_mesh ) throw(...)
{
	if ( max_verts_per_mesh < 0 )
	{
		throw "ummmm";	// $$$
	}

	MultiVerts		&verts = _geomp->GetVerts();
	Triangles		&trigs = _geomp->GetTrigs();

	if ( verts.GetPosN() < max_verts_per_mesh )
		return;

	verts.LockRW( __FILE__, __LINE__ );
	trigs.LockRW( __FILE__, __LINE__ );

	Vector3			bmin, bmax;
	float			substantial_distance;

	int	nv = verts.GetPosN();

	calc_mesh_bbox( bmin, bmax, verts.GetPosW(), nv );

	substantial_distance = (bmax-bmin).GetLength() / 500;

	std::vector<int>		trilist;
	bbox_c			bbox;

	TriIdx_VertIdx	tidx_vidx( _geomp );

	int	group_name_cnt = 0;

	for (int i=0; i < tidx_vidx.len(); ++i)
	{
		bbox.reset();

		trilist.clear();

		expand_bbox_by_connected_triangles( bbox,
											&trilist,
											verts.GetPosR(), tidx_vidx,
											&trigs._list.front(),
											i );
		if ( trilist.size() )
		{
			bbox.expand( substantial_distance );

			expand_bbox_by_contained_triangles( bbox,
												trilist,
												verts.GetPosR(),// tidx_vidx,
												&trigs._list.front(),
												trigs._list.size() );

			PASSERT( trilist.size() > 0 );
/*
			err = expand_bbox_by_connected_triangles( bbox, &trilist,
														gp->verts.GetPos(), tidx_vidx,
														gp->&trigs._list.front(),
														i );
			PSYS_ASSERTERR( err == 0 );
			PSYS_ASSERTERR( trilist.len() > 0 );
*/
			move_mesh_geom( trilist, ++group_name_cnt );
		}
	}

	eliminateBadTrigs();
	killUnusedPosVerts();

	// any self-respecting group should have all updated in the end
	UpdateGeometry();
	
	PASSERT( verts.GetPosN() == 0 );
	//_intflags |= REMOVE_TMP_FLG;

	verts.Unlock();
	trigs.Unlock();

}